/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package com.factory.server.algorithms;

//import org.jgrapht.EdgeFactory;
import com.factory.server.dto.EdgeDTO;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * Kruskaluv algoritmus
 *
 * @author Pavel Micka
 */
public class Kruskal {

    /**
     * Nalezne minimalni kostru neorientovaneho grafu o n uzlech (cisla uzlu 0,
     * 1, ..., n-1)
     *
     * @param edges hrany neorientovaneho grafu
     * @param nodeCount pocet uzlu neorientovaneho grafu (n)
     * @return minimalni kostra
     */
    public GraphProblemresult execute(List<EdgeDTO> edges, int nodeCount) {
        GraphProblemresult problemresult = new GraphProblemresult();
        DisjointSet ds = new DisjointSet(nodeCount);
        List<EdgeDTO> spanningTree = new ArrayList<EdgeDTO>();
        Collections.sort(edges);
        int i = 0;
        int cost = 0;
        while (i != edges.size() && spanningTree.size() != nodeCount - 1) {
            EdgeDTO e = edges.get(i);
            if (ds.find(e.getSource()) != ds.find(e.getTarget())) {
                spanningTree.add(e);
                ds.union(e.getSource(), e.getTarget());
                cost += e.getCost();
            }
            i++;
        }
        problemresult.setSpanningTree(spanningTree);
        problemresult.setCost(cost);
        return problemresult;
    }

// ***************************** //
// *     DATOVE STRUKTURY      * //
// ***************************** //
    /**
     * Jednoducha implementace Union-Find problemu
     *
     * @author Pavel Micka
     */
    class DisjointSet {

        private Node[] nodes;

        public DisjointSet(int nodeCount) {
            nodes = new Node[nodeCount];
            for (int i = 0; i < nodeCount; i++) {
                nodes[i] = new Node();
                nodes[i].id = i;
            }
        }

        /**
         * Provede sjednoceni komponent, ve kterych jsou uzly "a" a "b" Union
         * provadi vzdy do A
         *
         * @param a cislo uzlu a
         * @param b cislo uzlu b
         * @return cislo reprezentanta sjednocene komponenty
         */
        public int union(int a, int b) {
            Node repA = nodes[find(a)];
            Node repB = nodes[find(b)];

            repB.parent = repA;
            return repA.id;
        }

        /**
         * Vrati reprezentanta zadaneho uzlu
         *
         * @param a cislo uzlu, jehoz reprezentanta hledame
         * @return cislo reprezentanta uzlu
         */
        public int find(int a) {
            Node n = nodes[a];
            int jumps = 0;
            while (n.parent != null) {
                n = n.parent;
                jumps++;
            }
            if (jumps > 1) {
                repair(a, n.id);
            }
            return n.id;
        }

        /**
         * Provede opravu (compression) cesty
         *
         * @param a
         * @param rootId
         */
        private void repair(int a, int rootId) {
            Node curr = nodes[a];
            while (curr.id != rootId) {
                Node tmp = curr.parent;
                curr.parent = nodes[rootId];
                curr = tmp;
            }
        }

        @Override
        public String toString() {
            StringBuilder builder = new StringBuilder();
            for (int i = 0; i < nodes.length; i++) {
                builder.append(find(i) + " ");
            }
            return builder.toString();
        }

        /**
         * Uzel n-arniho stromu
         */
        private class Node {

            /**
             * Rodic
             */
            Node parent;
            /**
             * Identifikator uzlu
             */
            int id;
        }
    }
}
